﻿//https://leetcode.cn/problems/valid-triangle-number/

//暴力解法
class Solution {
public:
	int triangleNumber(vector<int>& nums) {
		// 1. 排序
		sort(nums.begin(), nums.end());
		int n = nums.size(), ret = 0;
		// 2. 从⼩到⼤枚举所有的三元组
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					// 当最⼩的两个边之和⼤于第三边的时候，统计答案
					if (nums[i] + nums[j] > nums[k])
						ret++;
				}
			}
		}
		return ret;
	}
};
class Solution {
public:
	int triangleNumber(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int a = 0, b = 0, c = 0;
		int count = 0;
		for (int i = 0; i < nums.size(); ++i)
		{
			for (int j = i + 1; j< nums.size() && j > i; ++j)
			{
				//cout<<i<<" "<<j<<" "<<endl;

				a = nums[i];
				b = nums[j];
				for (int k = nums.size() - 1; k >= 0 && k > j; --k)
				{
					c = nums[k];
					//cout<<i<<" "<<j<<" " <<k<<" | ";
					//cout<<a<<" "<<b<<" " <<c<<endl;     
					if (a + b > c)
					{
						count += k - j;
						break;
					}
				}
			}
		}
		return count;
	}
};
//我的
class Solution {
public:
	int triangleNumber(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int left, right, tail = nums.size() - 1;
		int count = 0;
		for (left = 0, right = tail - 1; tail >= 2; --tail)
		{
			left = 0; right = tail - 1;
			//cout<<left<<" "<<right<<" "<<tail<<endl;
			while (left < right)
			{
				//cout<<left<<" "<<right<<" "<<tail<<endl;
				//数组已排序，若成立，b、c边固定，left到right的的位置取的a边都成立
				if (nums[left] + nums[right] > nums[tail])
				{
					count += right - left;
					--right;
				}
				//a + b > c不成立 -》 a太小了（b是从大到小，a是从小到大）              
				else ++left;

			}
		}
		return count;
	}
};
//答案
class Solution
{
public:
	int triangleNumber(vector<int>& nums)
	{
		// 1. 优化
		sort(nums.begin(), nums.end());
		// 2. 利⽤双指针解决问题
		int ret = 0, n = nums.size();
		for (int i = n - 1; i >= 2; i--) // 先固定最⼤的数
		{
			// 利⽤双指针快速统计符合要求的三元组的个数
			int left = 0, right = i - 1;
			while (left < right)
			{
				if (nums[left] + nums[right] > nums[i])
				{
					ret += right - left;
					right--;
				}
				else
				{
					left++;
				}
			}
		}
		return ret;
	}
};